#include "template.h"
/* trie结构体定义 */
/* nex二维数组用于存储每个节点的子节点指针，cnt用于记录节点总数，exist数组用于标记节点是否代表一个单词的结尾 */
struct trie {
    int nex[100000][26], cnt;
    bool exist[100000];  // 该结点结尾的字符串是否存在

    /* 插入函数，用于将一个字符串插入到trie中 */
    /* 参数s为待插入的字符串，l为字符串长度 */
    void insert(char *s, int l) {  // 插入字符串
        /* p用于记录当前节点的索引 */
        int p = 0;
        /* 遍历字符串的每个字符 */
        for (int i = 0; i < l; i++) {
            /* c用于计算当前字符对应的子节点索引 */
            int c = s[i] - 'a';
            /* 如果当前节点的子节点c不存在，则创建该子节点，并更新节点总数 */
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
            /* 更新当前节点索引到子节点c */
            p = nex[p][c];
        }
        /* 标记当前节点为一个单词的结尾 */
        exist[p] = 1;
    }

    /* 查找函数，用于判断一个字符串是否存在于trie中 */
    /* 参数s为待查找的字符串，l为字符串长度 */
    /* 返回值为1表示字符串存在，0表示字符串不存在 */
    bool find(char *s, int l) {  // 查找字符串
        /* p用于记录当前节点的索引 */
        int p = 0;
        /* 遍历字符串的每个字符 */
        for (int i = 0; i < l; i++) {
            /* c用于计算当前字符对应的子节点索引 */
            int c = s[i] - 'a';
            /* 如果当前节点的子节点c不存在，则字符串肯定不存在于trie中，返回0 */
            if (!nex[p][c]) return 0;
            /* 更新当前节点索引到子节点c */
            p = nex[p][c];
        }
        /* 返回当前节点是否标记为单词的结尾 */
        return exist[p];
    }
};
